1. Field of the Invention
This invention relates to a method of and apparatus for generating mask layouts (also called mask patterns) using, for example, computer-aided design (CAD), and more particularly to a compaction method and apparatus for symbolic layouts.
2. Description of the Related Art
A layout of an integrated circuit as shown in FIG. 8A is generally called a symbolic layout because it is expressed by symbols. Compaction or spacing techniques for such symbolic layouts involve shortening the distance between symbols as possible as design rules permit to produce a high packing-density layout or generate a layout meeting the design rules from a layout not meeting the design rules. Specifically, with these techniques, components including contact symbols 81 and wires 82 are compacted by moving them as shown in FIGS. 8B and 8C, so that the distance 1 between contact symbols 81, 81 may be shortened according to design rules as shown in FIG. 8C.
The compaction is broadly divided into two-dimensional compaction whereby components are moved two-dimensionally and one-dimensional compaction whereby components are moved one-dimensionally in each direction of x and y. Since two-dimensional compaction requires a huge amount of processing time, it is not in common use. For this reason, one-dimensional compaction is generally used. FIG. 8B shows the result of one-dimensional compaction of the FIG. 8A layout in the x-direction. As seen from FIG. 8B, with one-dimensional compaction, one compaction allows only either the x or the y coordinates of the components to change but prevents the other coordinates from changing.
The one-dimensional compaction is further classified into three methods: a shear line method (or known as a compression ridge method), a virtual grid method, and a constraint graph method (or known as a relative grid method). Among them, the constraint graph method is the most widely used. The technical aspects of these methods are well known, so that their explanation will be omitted.
The compaction described above, however, have the problem that they cannot process a huge amount of data, or an enormous amount of symbolic layouts. The reason for this is that although the amount of computer resources used in compaction processing, especially the frequency of use of the main memory increases as the size of an integrated circuit to be processed becomes larger, there is a limit to the capacity of the main memory. Therefore, all the chips on a large-scale integrated circuit cannot be compacted in unison.
Dependence of software performing compaction, or a compactor, on the circuit size is lower than order (n) (hereinafter, referred to as O(n)). Thus, if the dependence is O(f(n)), the upper limit of the circuit size allowing compaction is not so large. Specifically, when an ordinary design-supporting apparatus, for example, an engineering work station (EWS) with a main memory of the order of 32 MB, is used, the maximum size of an integrated circuit that a conventional compactor using the constraint graph method can handle at a time is a size containing approximately 10,000 transistors. Here, the value contains an error of the order of units. At present, large-scale integrated circuits contain several hundred thousand transistors. Thus, 10,000 transistors are much fewer in number than the several hundred thousand transistors.
As described above, since it is difficult to process a large-scale integrated circuit at a time using a conventional compactor, a hierarchically processing method has been proposed. As this hierarchically processing method, a bottom-up method and a pitch matching method are well known. The bottom-up method is such that a symbolic layout is divided into segments 91 and 92 as low-level hierarchical data items as shown in FIG. 9, and after these segments 91 and 92 are subjected to compaction, the connection terminals of the respective segments 91 and 92 are connected to one another with wires 93.
The pitch matching method is such that a symbolic layout is divided into segments 101 and 103 and these segments 101 and 103 undergo compaction, taking into account the pitch of wires connecting the segments 101 and 102.
The first problem of the hierarchically processing method is that compaction between different hierarchies or between different blocks in the same hierarchy is insufficient, that is, an area loss takes place. For example, in the case of the bottom-up method of FIG. 9, a wasteful wiring area develops. The second problem is implementation is complex and difficult and consequently a practical system has not been placed on the market yet.
Another problem with conventional compaction methods is that it is difficult to predict the performance or the result of the compaction processing. Particularly, conventional methods introduce the danger of permitting a relative position between symbols to be displaced much from the original position. If this happens, the delay time in the wire will increase more than expected. Thus, it is difficult to predict the performance of the chip unless steps are taken to prevent the displacements of the symbols.
Further, the inventor of this application has disclosed a compaction method in the literature: Proc. 27th ACM/IEEE Design Automation Conference pp. 388-393. The technique disclosed in the literature is related to a compaction method of a logic gate integrated circuit where the control lines for supplying control signals are arranged perpendicularly to data lines for supplying data, or a compaction method of data paths. In this compaction method, the input data to the symbolic layout has been previously divided so as to form a hierarchy, which restricts description of input data, resulting in lack of versatility.